package P1389;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * Problema da disciplina de Estrutura de Dados e Complexidade de Algoritmos da
 * Pos Graduacao do Periodo 2011.1
 *
 * @see http://br.spoj.pl/problems/DESCULPA/
 * @author Elenilson Vieira - 111100371 - elenilson[at]elenilsonvieira.com
 * @since 1 de junho de 2011
 */
public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        String line = null;
        int testNumber = 1;

        while (!(line = reader.readLine().trim()).equals("0 0")) {
            int sorryAmountOnCard = -1;
            String data[] = line.split(" ");
            int cardSize = Integer.parseInt(data[0]);
            int phrasesAmount = Integer.parseInt(data[1]);
            int charsAmountOnPhrases[] = new int[phrasesAmount];
            int sorryAmountOnPhrases[] = new int[phrasesAmount];

            for (int i = 0; i < phrasesAmount; i++) {
                line = reader.readLine();
                data = line.split(" ");
                charsAmountOnPhrases[i] = Integer.parseInt(data[0]);
                sorryAmountOnPhrases[i] = Integer.parseInt(data[1]);
            }

            sorryAmountOnCard = booleanKnapsackAdapted(charsAmountOnPhrases, sorryAmountOnPhrases, cardSize);
            System.out.println(String.format("Teste %d\n%d\n", testNumber++, sorryAmountOnCard));

//            sorryAmountOnCard = booleanKnapsackAdapted2(charsAmountOnPhrases, sorryAmountOnPhrases, cardSize);
//            System.out.println(String.format("Teste %d\n%d\n", testNumber++, sorryAmountOnCard));
//
//            sorryAmountOnCard = booleanKnapsackAdapted3(phrasesAmount, cardSize, charsAmountOnPhrases, sorryAmountOnPhrases);
//            System.out.println(String.format("Teste %d\n%d\n", testNumber++, sorryAmountOnCard));
        }
    }

    /**
     * Implementacao do problema da mochila booleana adaptado para o problema
     * das desculpas
     *
     * @param w os pesos
     * @param c os valores
     * @param W a capacidade da mochila
     * 
     * @see http://www.ic.unicamp.br/~rezende/ensino/mo417/2010s2/Slides/Aula13.pdf
     *
     * @return a qua a quantidade de desculpas
     */
    private static int booleanKnapsackAdapted2(int[] w, int[] c, int W) {
        int n = w.length;
        int[][] z = new int[n + 1][W + 1];

        for (int k = 1; k <= n; k++) {
            for (int d = 1; d <= n; d++) {
                if (w[k] > d) {
                    z[k][d] = z[k - 1][d];
                } else {
                    if ((c[k] + z[k - 1][d - w[k]]) > z[k - 1][d]) {
                        z[k][d] = c[k] + z[k - 1][d - w[k]];
                    } else {
                        z[k][d] = z[k - 1][d];
                    }
                }
            }
        }

        int[] solution = knapsackSolution(z, n, W, w);

        for (int i : solution) {
            System.out.print(String.format("%d ", i));
        }

        return -1;
    }

    /**
     * Implementacao do problema da mochila booleana adaptado para o problema
     * das desculpas
     *
     * @param weights os pesos
     * @param values os valores
     * @param capacity a capacidade da mochila
     *
     * @see http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/solucoes/mochila-bool2.html
     *
     * @return a qua a quantidade de desculpas
     */
    private static int booleanKnapsackAdapted(int[] weights, int[] values, int capacity) {
        int t[][] = new int[weights.length + 1][capacity + 1];

        int b = 0;
        for (b = 0; b <= capacity; b++) {
            for (int i = 1; i <= weights.length; i++) {
                int a = t[i - 1][b];
                int aLine = weights[i - 1] > b ? 0 : t[i - 1][b - weights[i - 1]] + values[i - 1];
                t[i][b] = a > aLine ? a : aLine;
            }
        }

        b = capacity;
        int sorriesAmount = 0;

        for (int i = weights.length; i > 0; i--) {
            if (t[i][b] != t[i - 1][b]) {
                sorriesAmount += values[i - 1];
                b -= weights[i - 1];
            }
        }

        return sorriesAmount;
    }

    /**
     * Problema da mochila adaptado pra o problema das desculpas. Esse nao e'
     * uma implementacao minha, foi copiado da fonte com apenas adaptacoes.
     *
     * @param numItems a quantidade de itens
     * @param maxWeight o maximo de peso da mochila
     * @param weight os pesos dos objetos
     * @param benefit os valores dos objetos
     *
     * @see http://www.csc.liv.ac.uk/~martin/teaching/comp202/Java/Knapsack-code.html
     *
     * @return a quantidade de desculpas
     */
    private static int booleanKnapsackAdapted3(int numItems, int maxWeight, int weight[], int[] benefit) {
        int[][] B = new int[numItems + 1][maxWeight + 1];

        for (int k = 1; k <= numItems; k++) {
            for (int w = maxWeight; w >= weight[k]; w--) {
                if (benefit[k] + B[k - 1][w - weight[k]] > B[k - 1][w]) {
                    B[k][w] = benefit[k] + B[k - 1][w - weight[k]];
                } else {
                    B[k][w] = B[k - 1][w];
                }
            }
            for (int w = 0; w < weight[k]; w++) {
                B[k][w] = B[k - 1][w];
            }
        }

        int valueIntoKnapsack = 0;
        for (int k = numItems, remainingWeight = maxWeight; k > 0; k--) {
            if (remainingWeight >= weight[k]) {
                if (B[k][remainingWeight] == (benefit[k] + B[k - 1][remainingWeight - weight[k]])) {
                    valueIntoKnapsack += benefit[k];
                    remainingWeight -= weight[k];
                }
            }
        }

        return valueIntoKnapsack;
    }

    /**
     * Parte da solucao do problema da mochila 2
     *
     * @param z a tabela preenchida
     * @param n o numero de itens
     * @param W a capacidade da mochila
     * @param w os pesos dos itens
     *
     * @return os itens colocados na mochila
     */
    private static int[] knapsackSolution(int[][] z, int n, int W, int w[]) {
        int x[] = new int[n + 1];

        knapsackSolutionAux(x, z, n, W, w);

        return x;
    }

    /**
     * Metodo auxiliar (para recursao) utilizado pelo knapsackSolution
     *
     * @param x um array a ser preenchido com as solucoes
     * @param z a tabela
     * @param k o numero de itens
     * @param d a capacidade da mochila
     * @param w o array de pesos dos itens
     */
    private static void knapsackSolutionAux(int[] x, int[][] z, int k, int d, int w[]) {
        if (k != 0) {
            if (z[k][d] == z[k - 1][d]) {
                x[k] = 0;
                knapsackSolutionAux(x, z, k - 1, d, w);
            } else {
                x[k] = 1;
                knapsackSolutionAux(x, z, k - 1, d - w[k], w);
            }
        }
    }
}
